1. Field of the Invention
The present invention relates to a digital information processing technique and, more particularly, to a vector quantization method and a vector quantization apparatus therefor.
2. Description of the Related Art
When, for example, images or speech sounds are expressed as functions, quantization generally means discretization in a specific value range. That is, quantization means that continuous functions, on sampling points, obtained by sampling, are expressed by a finite number of values. As a practical quantization method, a vector quantization method is available.
In this vector quantization method, for example, an input image is divided into a plurality of blocks, and quantization is performed with respect to one vector constituted by pixels of each block as components. For example, in a specific block, several representative patterns (representative vectors) which are considered to have high frequencies of occurrence are determined, and identification codes are respectively assigned thereto. These representative patterns are stored in an encoder, which is called a code book. Upon reception of an input signal, the code book is searched in units of blocks to find a representative vector most similar to the pattern of the input signal, and the corresponding identification code is output. Such a method is equally applied to speech and the like.
In order to realize high-speed processing, a vector quantization apparatus for executing such vector quantization uses, for example, a tree search method (A. Buzo, A. H. Gray. Jr., R. M. Gray, and J. D. Markel, "Speech coding based upon vector quantization", IEEE Trans. Acoust., Speech & Signal Process., ASSP-28, 10, pp. 562-574, October, 1980), in which a structural code book is used to reduce the number of vectors to be searched.
In addition, as methods of reducing the number of strain (i.e., distance) calculations used for vector quantization, a method of changing the order of search in accordance with the probabilities of occurrence of vectors, and a method of using an intra-vector mean value to interrupt a search have been proposed. With these methods, high-speed vector quantization has been realized.
Of the vector quantization methods described above, the tree search method allows high-speed processing in strain calculations as compared with other methods. However, in this method, if an input vector is present near the boundary between subspaces, an optimal vector cannot be obtained from a code book. Therefore, the tree search method lacks accuracy in terms of the minimization of strain.
In the method of reducing the number of strain calculations, comparison or some processing must be performed with respect to all code book vectors at least once for each.
In the method of performing a search in an order preset in accordance with the probabilities of occurrence of vectors, if the probabilities of vectors are different from those in a code book, it takes much time to reach an optimal vector located at a position near the end. This may cause a great deterioration in efficiency of strain calculations.
In the method of using an intra-vector mean value as a search interruption condition, if vectors having similar characteristics concentrate in a small distribution range, the difference between intra-vector mean values is reduced. If the difference becomes smaller than a preset value, the condition cannot be satisfied, and a search interruption may be not determined.
In the above-described conventional search methods, an optimal, efficient, high-speed search for a code book vector corresponding to an input vector cannot be performed depending on the characteristics of the input vector.